'''
def hanoi(n, A, B, C):
    if n == 1:
        move(1, A, C)
    else:
        # 经由C，将A上n - 1个先移到B
        hanoi(n - 1, A, C, B)
        # 将第n个，也就是最大的那个，移到C
        move(n, A, C)
        # 此时A空了，可以从B经由A将n - 1个再移到C
        hanoi(n - 1, B, A, C)
def move(n, A, B):
    global m, l
    m += 1
    l += n
    print(f"第{m}次移动，把第{n}号盘从{A}移到{B}")
m, l = 0, 0
n = int(input())
hanoi(n, 'A', 'B', 'C')
print(m, l)

1
第1次移动，把第1号盘从A移到C
1 1
--------------------------------
2
第1次移动，把第1号盘从A移到B
第2次移动，把第2号盘从A移到C
第3次移动，把第1号盘从B移到C
3 4
--------------------------------
3
第1次移动，把第1号盘从A移到C
第2次移动，把第2号盘从A移到B
第3次移动，把第1号盘从C移到B
第4次移动，把第3号盘从A移到C
第5次移动，把第1号盘从B移到A
第6次移动，把第2号盘从B移到C
第7次移动，把第1号盘从A移到C
7 11
--------------------------------
直接通过递归的话，前面还很快速。但是，如果递归层数太多的话，就会很慢。

这时，我们发现，这个很符合我们之前提到的递归中有2次子递归的情况，时间复杂度为2的n次方！
而同时，我们发现传递盘子的名字是一件没有意义的事情，我们只要传递盘子号或者说盘子个数就可以了。
于是我们可以把它简化一下。

'''
'''
def hanoi(n):
    if n == 1:
        move(1)
    else:
        hanoi(n - 1)
        move(n)
        hanoi(n - 1)
def move(n):
    global m, l
    m += 1
    l += n
m, l = 0, 0
n = int(input())
hanoi(n)
print(m, l)

2
3 4
-----------
3
7 11
-----------

结果是一样的！
同时，我们发现，move前后，递归的都是hanoi(n - 1)，是一样的，那么你想到了什么？
对，记忆化！我们尝试使用记忆化来解决时间复杂度太高的问题。
不过我们怎么知道m和l该加多少次呢？这需要对函数进行更深层的改造。

'''
'''
def hanoi(n):
    if n == 1:
        return move(1)
    else:
        # 没错，我们使用map进行列表加法，得出的结果就是步数和体力消耗
        # map其实不仅可以将输入转换成整数，他其实是一个对列表进行批量操作的函数
        # 而且可以操作多个列表。我们可以通过传入函数或者使用lambda表达式对列表进行操作
        # 下面这个列子传入3个列表，他们的形式都是(1, 1)这样的两个元素的元组
        # 而lambda x, y, z代表他们三个中的同一索引的元素。
        # 冒号后面的值，就是新的map对象的该索引的元素的值。因为我们想要列表的同一位置相加
        # 所以直接lambda x, y, z: x + y + z就可以了。
        return tuple(map(lambda x, y, z: x + y + z, hanoi(n - 1), move(n), hanoi(n - 1)))

def move(n):
    return 1, n
'''
'''
def hanoi(n):
    if n == 1:
        return (1, 1)
    else:
        # 我们甚至不需要move函数了，因为它无非就是返回一个(1, n)元组
        return tuple(map(lambda x, y, z: x + y + z, hanoi(n - 1), (1, n), hanoi(n - 1)))
'''

def hanoi(n):
    if n == 1:
        return (1, 1)
    else:
        # 而我们知道加法是满足交换律和结合律的，所以，继续简写
        return tuple(map(lambda x, y: x * 2 + y, hanoi(n - 1), (1, n)))
# 虽然好像跟刚刚说的记忆化搜索有点差别，但是我们成功地把它优化成只有一个子递归了！
# 也就是说，它的时间复杂度只有O(n)了，我们已经可以直接提交了！
# 说实话还是挺有成就感的哈哈哈，我竟然一步步优化成功了
m, l = 0, 0
t = int(input())
for i in range(t):
    n = int(input())
    m, l = hanoi(n)
    print(m, l)
'''
# 最后，这个题其实是有O(1)的解法的，就是通过数学推导，将计算的式子简化成一个平方的式子还是啥的，我忘了。
# 我能推导到前面那些已经不容易了哈哈哈，能解题了就行。你们感兴趣的可以自己尝试推一下。。
# 好像步数就是2的n次方-1
'''
# -------------------------------------------------------------------------------

# 比赛环境为python3.8.6版本自带的IDLE，最好早点熟悉一下。。这个东西的提示时有时无

# 菜单栏最右边的Help的Python Docs 比赛时候也可以看，不过建议还是提前多了解了解，

# 比赛的时候至少知道在文档找什么能用的上。

# IDLE是下载Python时自带的，在按住win+s搜索IDLE就能搜到了。

# 然后点左上角的File可以创建新文件，然后按F5可以运行。
